Search Results

Documents authored by Tokuyama, Takeshi

Document
DOI: 10.4230/LIPIcs.STACS.2022.58
High Quality Consistent Digital Curved Rays via Vector Field Rounding

Authors: Takeshi Tokuyama and Ryo Yoshimura

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
We consider the consistent digital rays (CDR) of curved rays, which approximates a set of curved rays emanating from the origin by the set of rooted paths (called digital rays) of a spanning tree of a grid graph. Previously, a construction algorithm of CDR for diffused families of curved rays to attain an O(√{n log n}) bound for the distance between digital ray and the corresponding ray is known [Chun et al., 2019]. In this paper, we give a description of the problem as a rounding problem of the vector field generated from the ray family, and investigate the relation of the quality of CDR and the discrepancy of the range space generated from gradient curves of rays. Consequently, we show the existence of a CDR with an O(log ^{1.5} n) distance bound for any diffused family of curved rays.
Cite as

Takeshi Tokuyama and Ryo Yoshimura. High Quality Consistent Digital Curved Rays via Vector Field Rounding. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 58:1-58:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{tokuyama_et_al:LIPIcs.STACS.2022.58,
  author =	{Tokuyama, Takeshi and Yoshimura, Ryo},
  title =	{{High Quality Consistent Digital Curved Rays via Vector Field Rounding}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{58:1--58:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.58},
  URN =		{urn:nbn:de:0030-drops-158680},
  doi =		{10.4230/LIPIcs.STACS.2022.58},
  annote =	{Keywords: Computational Geometry, Discrepancy Theory, Consistent Digital Rays, Digital Geometry}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.34
Distance Bounds for High Dimensional Consistent Digital Rays and 2-D Partially-Consistent Digital Rays

Authors: Man-Kwun Chiu, Matias Korman, Martin Suderland, and Takeshi Tokuyama

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We consider the problem of digitalizing Euclidean segments. Specifically, we look for a constructive method to connect any two points in ℤ^d. The construction must be consistent (that is, satisfy the natural extension of the Euclidean axioms) while resembling them as much as possible. Previous work has shown asymptotically tight results in two dimensions with Θ(log N) error, where resemblance between segments is measured with the Hausdorff distance, and N is the L₁ distance between the two points. This construction was considered tight because of a Ω(log N) lower bound that applies to any consistent construction in ℤ². In this paper we observe that the lower bound does not directly extend to higher dimensions. We give an alternative argument showing that any consistent construction in d dimensions must have Ω(log^{1/(d-1)} N) error. We tie the error of a consistent construction in high dimensions to the error of similar weak constructions in two dimensions (constructions for which some points need not satisfy all the axioms). This not only opens the possibility for having constructions with o(log N) error in high dimensions, but also opens up an interesting line of research in the tradeoff between the number of axiom violations and the error of the construction. In order to show our lower bound, we also consider a colored variation of the concept of discrepancy of a set of points that we find of independent interest.
Cite as

Man-Kwun Chiu, Matias Korman, Martin Suderland, and Takeshi Tokuyama. Distance Bounds for High Dimensional Consistent Digital Rays and 2-D Partially-Consistent Digital Rays. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 34:1-34:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chiu_et_al:LIPIcs.ESA.2020.34,
  author =	{Chiu, Man-Kwun and Korman, Matias and Suderland, Martin and Tokuyama, Takeshi},
  title =	{{Distance Bounds for High Dimensional Consistent Digital Rays and 2-D Partially-Consistent Digital Rays}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{34:1--34:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.34},
  URN =		{urn:nbn:de:0030-drops-129002},
  doi =		{10.4230/LIPIcs.ESA.2020.34},
  annote =	{Keywords: Consistent Digital Line Segments, Digital Geometry, Discrepancy}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.32
Consistent Digital Curved Rays and Pseudoline Arrangements

Authors: Jinhee Chun, Kenya Kikuchi, and Takeshi Tokuyama

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Representing a family of geometric objects in the digital world where each object is represented by a set of pixels is a basic problem in graphics and computational geometry. One important criterion is the consistency, where the intersection pattern of the objects should be consistent with axioms of the Euclidean geometry, e.g., the intersection of two lines should be a single connected component. Previously, the set of linear rays and segments has been considered. In this paper, we extended this theory to families of curved rays going through the origin. We further consider some psudoline arrangements obtained as unions of such families of rays.
Cite as

Jinhee Chun, Kenya Kikuchi, and Takeshi Tokuyama. Consistent Digital Curved Rays and Pseudoline Arrangements. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chun_et_al:LIPIcs.ESA.2019.32,
  author =	{Chun, Jinhee and Kikuchi, Kenya and Tokuyama, Takeshi},
  title =	{{Consistent Digital Curved Rays and Pseudoline Arrangements}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{32:1--32:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.32},
  URN =		{urn:nbn:de:0030-drops-111538},
  doi =		{10.4230/LIPIcs.ESA.2019.32},
  annote =	{Keywords: Computational Geometry, Digital Geometry, Spanning Tree, Graph Drawing}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ISAAC.2017
LIPIcs, Volume 92, ISAAC'17, Complete Volume

Authors: Yoshio Okamoto and Takeshi Tokuyama

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
LIPIcs, Volume 92, ISAAC'17, Complete Volume
Cite as

28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Proceedings{okamoto_et_al:LIPIcs.ISAAC.2017,
  title =	{{LIPIcs, Volume 92, ISAAC'17, Complete Volume}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017},
  URN =		{urn:nbn:de:0030-drops-82924},
  doi =		{10.4230/LIPIcs.ISAAC.2017},
  annote =	{Keywords: Data Structures, Theory of Computation, Mathematics of Computing, Computing Methodologies}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ISAAC.2017.0
Front Matter, Table of Contents, Preface, External Reviewers

Authors: Yoshio Okamoto and Takeshi Tokuyama

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
Front Matter, Table of Contents, Preface, External Reviewers
Cite as

28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{okamoto_et_al:LIPIcs.ISAAC.2017.0,
  author =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  title =	{{Front Matter, Table of Contents, Preface, External Reviewers}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.0},
  URN =		{urn:nbn:de:0030-drops-82084},
  doi =		{10.4230/LIPIcs.ISAAC.2017.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, External Reviewers}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact